package cn.edu.xjtu.work.mergeInterval;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 56. 合并区间
 * 
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]
 * 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solu = new Solution();
        int[][] intervals = { { 1, 9 }, { 2, 5 }, { 19, 20 }, { 10, 11 }, { 12, 20 }, { 0, 3 }, { 0, 1 }, { 0, 2 } };
        System.out.println(Arrays.deepToString(solu.merge(intervals)));
    }

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        List<int[]> res = new ArrayList<>();
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= res.get(res.size() - 1)[1]) {
                int[] temp = res.remove(res.size() - 1);
                res.add(new int[] { Math.min(temp[0], intervals[i][0]), Math.max(intervals[i][1], temp[1]) });
            } else {
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[0][]);
    }
}
